package problem;

public class S_122 {
    //买卖股票的最佳时机2，交易次数没有限制
    //1.暴力，超时
    class Solution {
        public int maxProfit(int[] prices) {
            return calculate(prices,0);
        }
        public int calculate(int prices[],int s){
            if(s>=prices.length) return 0;
            int max=0;
            for(int start=s;start<prices.length;start++){
                int maxprofit=0;        //当天买该股票的最大收益
                for(int i=start+1;i<prices.length;i++){
                    if(prices[start]<prices[i]){
                        int profit=calculate(prices,i+1)+prices[i]-prices[start];
                        if(profit>maxprofit) maxprofit=profit;
                    }
                }
                if(maxprofit>max) max=maxprofit;
            }
            return max;
        }
    }

    //2.峰谷法
    class Solution1{
        public int maxProfit(int[] prices){
            if(prices==null||prices.length==0) return 0;
            int vally=prices[0];    //谷
            int peak=prices[0];     //峰
            int i=0;    //  索引遍历
            int maxprofit=0;
            while(i<prices.length-1){
                while(i < prices.length - 1 && prices[i] >= prices[i + 1]) i++;
                vally=prices[i];    //找到第一个谷
                while(i < prices.length - 1 && prices[i] <= prices[i + 1]) i++;
                peak=prices[i];     //找到第一个峰
                maxprofit+=peak-vally;
            }
            return maxprofit;
        }
    }

    //3.简单的一次遍历
    class Solution2 {
        public int maxProfiit(int[] prices) {
            if (prices == null || prices.length == 0) return 0;
            int maxprofit = 0;
            for (int i = 1; i < prices.length; i++) {
                if (prices[i] >= prices[i - 1])
                    maxprofit += prices[i] - prices[i - 1];
            }
            return maxprofit;
        }
    }
}
